from bisect import bisect_left, bisect_right

# 演示：通过上界和下界求目标值的总个数
a = [ 1, 2, 3, 3, 3, 4, 5, 6 ]
t = 3
lb = bisect_left(a, t)
ub = bisect_right(a, t) - 1
print('数组搜索的下界是', lb) 
print('数组搜索的上界是', ub) 
print('目标元素总共有', ub - lb + 1, '个')

# public class BinarySearchSolution {
#     /**
#      * 下界模板
#      * 下界的定义：数组中大于等于target的第一个元素下标位置
#      * 当target存在多个时，下界取到最左边的元素
#      * 当target不存在时，下界表示target在排序数组中的插入位置
#      */
#     int lowerBound(int[] nums, int target) {
#         int left = 0, right = nums.length - 1;
#         while (left < right) {
#             // 注意这里不要记错成上界模板的(left+right+1)/2，否则同样可能陷入死循环
#             int mid = (left + right) / 2; 
#             if (nums[mid] < target)
#                 left = mid + 1;
#             else 
#                 right = mid;
#         }
#         return left;
#     }

#     /**
#      * 上界模板
#      * 上界的定义：数组中小于等于target的最后一个元素下标位置
#      * 当target存在多个时，上界取到最右边的元素
#      * 当target不存在时，上界表示target在排序数组中的插入位置之前的位置
#      */
#     int upperBound(int[] nums, int target) {
#         int left = 0, right = nums.length - 1;
#         while (left < right) {
#             // 小心可能陷入死循环，记得上界模板中mid的计算需要+1
#             int mid = (left + right + 1) / 2; 
#             if (nums[mid] > target)
#                 right = mid - 1;
#             else 
#                 left = mid;
#         }
#         return left;
#     }

#     // 演示：通过上界和下界求目标值的总个数
#     void test() {
#         int[] a = { 1, 2, 3, 3, 3, 4, 5, 6 };
#         int t = 3;
#         int lb = lowerBound(a, t), ub = upperBound(a, t);
#         System.out.println("数组搜索的下界是" + lb 
#            + ", 上界是" + ub 
#            + ", 目标元素总共有" + (ub - lb + 1) + "个");
#     }

#     public static void main(String[] args) {
#         BinarySearchSolution sln = new BinarySearchSolution();
#         sln.test();
#     }
# }
